package 第七周;

/*
 * @author  YxinMiracle
 * @date  2022-05-06 20:22
 * @Gitee: https://gitee.com/yxinmiracle
 */

public class 编辑距离 {

    public int minDistance(String word1, String word2) {
        if (word1.equals("") && word2.equals("")) return 0;
        int m = word1.length();
        int n = word2.length();
        word1 = " " + word1;
        word2 = " " + word2;
        /**
         * int[i][j]
         * 表示前i个字符变成前j个字符需要改变的次数
         *
         * 增加         删除             替换
         * ace         hor
         * ac          ro
         */
        int[][] f = new int[m + 1][n + 1];
        int max = Math.max(m, n);
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                f[i][j] = max;
            }
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                f[i][j] = Math.min(f[i][j - 1] + 1, Math.min(f[i - 1][j] + 1, f[i - 1][j - 1] + (word1.charAt(i) == word2.charAt(j) ? 0 : 1)));
            }
        }

        return f[m][n];

    }


}
